The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.

If the principle of optimality applies in a given problem, we can develop a recursive property that gives an optimal solution to an instance in terms of optimal solutions to subinstances. The important but subtle reason why we can then use dynamic programming to construct an optimal solution to an instance is that the optimal solutions to the subinstances can be any optimal solutions.

어떤 문제의 입력에 대한 최적 해가 그 입력을 나눈 부분에 대해서도 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다 라고 한다. 즉, 부분적인 최적 해가 전체 해안에 포함되어 있을때, 부분 해를 이용하여 최적 해를 찾을 수 있다는 뜻이다.

주어진 문제에 대해 최적의 원칙이 적용될 수 있어야 동적계획법으로 해결할 수 있다. 하지만 모든 최적화 문제를 동적 프로그래밍으로 해결할 수 있는 것은 아니다.

Example In case of the Shortest Paths problem we showed that if $v_k$ is a vertex on an optial path from $v_i$ to $v_j$, then the subpaths from $v_i$ to $v_k$ and from $v_k$ to $v_j$ must also be optmimal. Therefore, the optimal solution to the instance contains optimal solutions to all subinstances, and the principle of optimality applies.

최단경로를 구하는 문제에서, $v_k$를 $v_i$에서 $v_j$로 가는 최적 경로 상의 정점이라고 하면, $v_i$에서 $v_k$로 가는 부분경로와 $v_k$에서 $v_j$로 가는 부분경로도 반드시 최적이어야 한다. 모든 경우에 대해 위와 같은 성질을 만족하면 최적의 원칙을 준수하게 되므로 동적계획법을 사용하여 알고리즘을 구축할 수 있다.

(참고) 최적의 원칙이 적용되지 않는 예제

Consider the Longest Paths problem of finding the longest simple paths from each vertex to all other vertices. In the below figure, the optimal (longest) simple path from $v_1$ to $v_4$ is [$v_1, v_3, v_2, v_4$]. However, the subpath [$v_1, v_3$] is not an optimal (longest) path from $v_1$ to $v_3$ because Length([$v_1, v_3$]) = 1 and Length([$v_1, v_2, v_3$]) = 4. Therefore, the principle of optimality does not apply.

$v_1$에서 $v_4$로의 최장경로는 [$v_1, v_3, v_2, v_4$]=8가 된다. 하지만 이 경로의 부분 경로인 $v_1$에서 $v_3$으로의 최장경로는 [$v_1, v_3$]=1이 아니고, [$v_1, v_2, v_3$]=4이다. 따라서 최장경로 문제에서는 최적의 원칙이 적용되지 않는다.